<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>链表-LinkedList</title>
</head>

<body>
    <script>
        // 链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。下图展示了一个链表的结构:
        // append(element):向列表尾部添加一个新的项。
        // insert(position, element):向列表的特定位置插入一个新的项。
        // remove(element):从列表中移除一项。
        // indexOf(element):返回元素在列表中的索引。如果列表中没有该元素则返回-1。
        // removeAt(position):从列表的特定位置移除一项。
        // isEmpty():如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。 
        // size():返回链表包含的元素个数。与数组的length属性类似。 
        // toString():由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。

        function LinkedList() {
            var Node = function (element) {　　　　　　　　//新元素构造
                this.element = element;
                this.next = null;
            };
            var length = 0;
            var head = null;

            this.append = function (element) {
                var node = new Node(element);　　　　　　　　//构造新的元素节点
                var current;
                if (head === null) {　　　　　　　　　　　　　//头节点为空时  当前结点作为头节点
                    head = node;
                } else {
                    current = head;
                    while (current.next) {　　　　　　　　　　//遍历，直到节点的next为null时停止循环，当前节点为尾节点
                        current = current.next;
                    }
                    current.next = node;　　　　　　　　　　　　//将尾节点指向新的元素，新元素作为尾节点
                }
                length++;　　　　　　　　　　　　　　　　　　　　//更新链表长度
            };
            this.removeAt = function (position) {
                if (position > -1 && position < length) {
                    var current = head;
                    var index = 0;
                    var previous;
                    if (position == 0) {
                        head = current.next;
                    } else {
                        while (index++ < position) {
                            previous = current;
                            current = current.next;
                        }
                        previous.next = current.next;
                    }
                    length--;
                    return current.element;
                } else {
                    return null;
                }
            };
            this.insert = function (position, element) {
                if (position > -1 && position <= length) {　　　　　　　　//校验边界
                    var node = new Node(element);
                    current = head;
                    var index = 0;
                    var previous;
                    if (position == 0) {　　　　　　　　　　　　　　　　　　　　//作为头节点，将新节点的next指向原有的头节点。
                        node.next = current;
                        head = node;　　　　　　　　　　　　　　　　　　　　　　　　//新节点赋值给头节点
                    } else {
                        while (index++ < position) {
                            previous = current;
                            current = current.next;
                        }　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//遍历结束得到当前position所在的current节点，和上一个节点
                        previous.next = node;　　　　　　　　　　　　　　　　　　　　//上一个节点的next指向新节点  新节点指向当前结点，可以参照上图来看
                        node.next = current;
                    }
                    length++;
                    return true;
                } else {
                    return false;
                }

            };
            this.toString = function () {
                console.log(head)
                var current = head;
                var string = '';
                while (current) {
                    string += ',' + current.element;
                    current = current.next;
                }
                return string;
            };
            this.indexOf = function (element) {
                var current = head;
                var index = -1;
                while (current) {
                    if (element === current.element) {　　　　　　　　　　　　//从头节点开始遍历
                        return index;
                    }
                    index++;
                    current = current.next;
                }
                return -1;
            };
            this.size = function () {
                return length;
            }

        }
        let link = new LinkedList();
        link.append('a')
        link.append('q')
        link.append('w')
        link.append('e')
        link.append('r')
        link.append('t')
        link.insert(3, '3')
        link.insert(0, '0')
        console.log(link.toString())
    </script>
</body>

</html>